The invention pertains to machine vision and, more particularly, to methods for identifying sets of collinear points from an image.
Machine vision refers to the automated analysis of an image to determine characteristics of objects and other features shown therein. It is often employed in automated manufacturing lines, where images of components are analyzed to determine placement and alignment prior to assembly. Machine vision is also used for quality assurance. For example, in the pharmaceutical and food packing industries, images of packages are analyzed to insure that product labels, lot numbers, "freshness" dates, and the like, are properly positioned and legible.
In many machine vision applications, it is essential to identify sets of points that define lines and, more particularly, parallel or perpendicular lines. This is typically critical in determining the position and orientation of an imaged object. In electronic circuit board assembly, for example, integrated circuit chips and sockets must be precisely positioned before they can be soldered into place. Metallic solder pads feature predominantly in images of these components and, as such, are often used in determining chip location and orientation.
Objects whose image is to be analyzed by machine vision typically include calibration targets. Often a cross-shaped symbol or parallel array of dots, such a target facilitates determining the position and orientation of the object in the image. A calibration target can also be used to correlate the image reference frame with that of the motion stage or conveyor belt on which the imaged object is placed.
Regardless of whether they are formed by solder pads, calibration targets, or otherwise, there are several known approaches to the problem of finding parallel and perpendicular lines from an image. One of the best known techniques is the Hough transform. According to that technique, every point in the set "votes" into an accumulator array in parameter space. Parameter pairs with the sufficiently many votes are identified as lines. Though oft used, the Hough transform can require significant computation resources and time to carry out these tasks.
For small data sets, the art also suggests exhaustively partitioning the set of points into all possible combinations of candidate lines, and evaluating the "goodness" of each one, e.g., with a least squares test. This procedure is impractical for large data sets because the computational complexity grows rapidly with the number of points.
An object of this invention is to provide an improved machine vision methods and, particularly, improved methods for identifying sets of collinear points from an image.
A related object is to provide methods for identifying parallel and perpendicular lines from an image.
A further object is to provide such methods as can be readily implemented on conventional digital data processors or other conventional machine vision analysis equipment.
Yet still another object of the invention is to provide such methods that can rapidly analyze images without undue consumption of resources.